﻿#include<iostream>
using namespace std;
//#include<algorithm>
//#include<list>
#include<vector>
#include<string>
#include<stack>
#include<queue>

//215.数组中第K个大的元素
//https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

//优先级队列topk法
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        //堆topk方法
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);//迭代器构造k个元素的堆
        for (int i = k; i < nums.size(); ++i)//建小堆取第k个最大的
        {
            if (nums[i] > pq.top())
            {
                pq.pop();
                pq.push(nums[i]);
            }
        }//建堆完成后就是数中的前k个从小到大排列的数，堆顶就是第k大的数
        return pq.top();
    }
};